{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Walls and Gates"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: wallsAndGates"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #墙与门"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你被给定一个 <code>m × n</code> 的二维网格 <code>rooms</code> ，网格中有以下三种可能的初始化值：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>-1</code> 表示墙或是障碍物</li>\n",
    "\t<li><code>0</code> 表示一扇门</li>\n",
    "\t<li><code>INF</code> 无限表示一个空的房间。然后，我们用 <code>2<sup>31</sup> - 1 = 2147483647</code> 代表 <code>INF</code>。你可以认为通往门的距离总是小于 <code>2147483647</code> 的。</li>\n",
    "</ol>\n",
    "\n",
    "<p>你要给每个空房间位上填上该房间到 <strong>最近门的距离</strong> ，如果无法到达门，则填 <code>INF</code> 即可。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/03/grid.jpg\" style=\"width: 500px; height: 223px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]\n",
    "<strong>输出：</strong>[[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rooms = [[-1]]\n",
    "<strong>输出：</strong>[[-1]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rooms = [[2147483647]]\n",
    "<strong>输出：</strong>[[2147483647]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rooms = [[0]]\n",
    "<strong>输出：</strong>[[0]]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == rooms.length</code></li>\n",
    "\t<li><code>n == rooms[i].length</code></li>\n",
    "\t<li><code>1 <= m, n <= 250</code></li>\n",
    "\t<li><code>rooms[i][j]</code> 是 <code>-1</code>、<code>0</code> 或 <code>2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [walls-and-gates](https://leetcode.cn/problems/walls-and-gates/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [walls-and-gates](https://leetcode.cn/problems/walls-and-gates/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]', '[[-1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        directions = [[-1, 0], [1, 0], [0, 1], [0, -1]]\n",
    "        if len(rooms) != 0:\n",
    "            M, N = len(rooms), len(rooms[0])\n",
    "            queue = collections.deque([])\n",
    "            # find all gates\n",
    "            for m in range(M):\n",
    "                for n in range(N):\n",
    "                    if rooms[m][n] == 0:\n",
    "                        queue.append([m, n])\n",
    "            while queue:\n",
    "                m, n = queue.popleft()\n",
    "                for d in directions:\n",
    "                    md = m + d[0]\n",
    "                    nd = n + d[1]\n",
    "                    # if not (md < 0 or nd < 0 or md >= M or nd >= N or rooms[md][nd] != 2147483647):\n",
    "                        # pass\n",
    "                    if md >= 0 and nd >= 0 and md < M and nd < N and rooms[md][nd] == 2147483647:\n",
    "                        rooms[md][nd] = rooms[m][n] +1\n",
    "                        queue.append([md, nd])\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(len(rooms)):\n",
    "            for j in range(len(rooms[0])):\n",
    "                if rooms[i][j] == 0:\n",
    "                    self.bfs(rooms, i, j)\n",
    "        \n",
    "        \n",
    "    def bfs(self, rooms: List[List[int]], i: int , j: int) -> None:\n",
    "        level = 0\n",
    "        q = []\n",
    "        q.append((i, j))\n",
    "        while q:\n",
    "            qsize = len(q)\n",
    "            while qsize > 0:\n",
    "                i, j = q.pop(0)\n",
    "                if (0 <= i < len(rooms) and 0 <= j < len(rooms[0]) and rooms[i][j] >= level):\n",
    "                    rooms[i][j] = level\n",
    "                    q.append((i-1, j));\n",
    "                    q.append((i+1, j));\n",
    "                    q.append((i, j-1));\n",
    "                    q.append((i, j+1));\n",
    "                qsize -= 1\n",
    "            level += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        if not rooms or not len(rooms): return None\n",
    "        m, n = len(rooms), len(rooms[0])\n",
    "        que = deque()\n",
    "        neighbors = [(0, -1), (0, 1), (-1, 0), (1, 0)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if rooms[i][j] == 0:\n",
    "                    que.append((i,j))\n",
    "                    while len(que):\n",
    "                        r, c = que.popleft()\n",
    "                        for dr, dc in neighbors:\n",
    "                            if 0 <= r+dr < m and 0 <= c+dc < n and rooms[r+dr][c+dc] > rooms[r][c] + 1:\n",
    "                                rooms[r+dr][c+dc] = rooms[r][c] + 1\n",
    "                                que.append((r+dr, c+dc))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    INF = pow(2,31) - 1\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        if not rooms:\n",
    "            return\n",
    "        for i in range(len(rooms)):\n",
    "            for j in range(len(rooms[0])):\n",
    "                if rooms[i][j] == 0:\n",
    "                    A = deque([[i,j]])\n",
    "                    while A:\n",
    "                        a = A.popleft()\n",
    "                        for x,y in [[a[0]+1,a[1]], [a[0]-1,a[1]], [a[0],a[1]+1], [a[0],a[1]-1]]:\n",
    "                            if 0<=x<len(rooms) and 0<=y<len(rooms[0]) and rooms[x][y]>rooms[a[0]][a[1]] + 1:\n",
    "                                rooms[x][y] = rooms[a[0]][a[1]] + 1\n",
    "                                A.append([x,y])\n",
    "                    \n",
    "\n",
    "\n",
    "rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]\n",
    "Solution().wallsAndGates(rooms)            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        if not rooms: return\n",
    "        rows, cols = len(rooms), len(rooms[0])\n",
    "        directions = [(0, -1),(1,0), (0, 1), (-1, 0)] #上右下左四个方向\n",
    "\n",
    "        def bfs(r, c):\n",
    "            if rooms[r][c] != 0:\n",
    "                return\n",
    "            seen = set()\n",
    "            que.append((r,c))\n",
    "            while que:\n",
    "                next_list = []\n",
    "                while que:\n",
    "                    x, y = que.pop(0)\n",
    "                    for dx, dy in directions:\n",
    "                        if 0 <= x + dx < rows and 0 <= y+dy < cols and rooms[x+dx][y+dy] > 0 and (x+dx, y+dy) not in seen:\n",
    "                            rooms[x+dx][y+dy] = min(rooms[x+dx][y+dy], rooms[x][y] + 1)\n",
    "                            next_list.append((x+dx, y+dy))\n",
    "                            seen.add((x+dx, y+dy))\n",
    "                que.extend(next_list)\n",
    "\n",
    "        que = []\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                bfs(r, c)\n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        def is_valid(x, y):\n",
    "            return 0 <= x < s1 and 0 <= y < s2\n",
    "\n",
    "        def get_near(x, y):\n",
    "            res = []\n",
    "            for xx, yy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:\n",
    "                if is_valid(xx, yy) and rooms[xx][yy] > 0:\n",
    "                    res.append((xx, yy))\n",
    "            return res\n",
    "\n",
    "        if not rooms or not rooms[0]:\n",
    "            return\n",
    "\n",
    "        s1, s2 = len(rooms), len(rooms[0])\n",
    "\n",
    "        doors = []\n",
    "        for i1 in range(s1):\n",
    "            for i2 in range(s2):\n",
    "                if rooms[i1][i2] == 0:\n",
    "                    doors.append((i1, i2))\n",
    "\n",
    "        for door in doors:\n",
    "            queue = collections.deque([door])\n",
    "            while queue:\n",
    "                (i1, i2) = queue.popleft()\n",
    "                distance = rooms[i1][i2] + 1\n",
    "                for (j1, j2) in get_near(i1, i2):\n",
    "                    if rooms[j1][j2] > distance:\n",
    "                        rooms[j1][j2] = distance\n",
    "                        queue.append((j1, j2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        if not rooms:\n",
    "            return\n",
    "        INF =  2147483647\n",
    "        queue = []\n",
    "        M = len(rooms)\n",
    "        N = len(rooms[0])\n",
    "        directions = ((1,0),(-1,0),(0,1),(0,-1))\n",
    "        for m in range(M):\n",
    "            for n in range(N):\n",
    "                if rooms[m][n] == 0:\n",
    "                    queue.append((m, n, 0))\n",
    "        while(queue):\n",
    "            r,c,d = queue.pop(0)\n",
    "            for i,j in directions:\n",
    "                new_r,new_c = r+i,c+j\n",
    "                if 0<=new_r<M and 0<= new_c<N and INF == rooms[new_r][new_c]:\n",
    "                    rooms[new_r][new_c] = d + 1\n",
    "                    queue.append((new_r,new_c,d +1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        def bfs(i, j):\n",
    "            queue = collections.deque([[i, j, 0]])\n",
    "            while queue:\n",
    "                for _ in range(len(queue)):\n",
    "                    i, j, step = queue.pop()\n",
    "                    rooms[i][j] = step\n",
    "                    for x, y in [[-1, 0], [1, 0], [0, 1], [0, -1]]:\n",
    "                        if 0 <= i + x < row and 0 <= j + y < col and rooms[i + x][j + y] > step + 1:\n",
    "                            queue.append([i + x, j + y, step + 1])\n",
    "\n",
    "        row, col = len(rooms), len(rooms[0])\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if rooms[i][j] == 0:\n",
    "                    bfs(i, j)\n",
    "                    \n",
    "        return rooms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        def bfs(rooms,i,j,m,n):\n",
    "            \n",
    "            q = collections.deque()\n",
    "            q.append((i,j,0))\n",
    "            while q:\n",
    "                di,dj,v = q.popleft()\n",
    "                for ki,kj in [(di-1,dj),(di+1,dj),(di,dj-1),(di,dj+1)]:\n",
    "                    if 0<= ki < m and 0 <= kj < n and v + 1 < rooms[ki][kj] :\n",
    "                        q.append((ki,kj,v + 1))\n",
    "                        rooms[ki][kj] = v + 1\n",
    "\n",
    "        m,n = len(rooms), len(rooms[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if rooms[i][j] == 0:\n",
    "                    bfs(rooms,i,j,m,n)\n",
    "\n",
    "\n",
    "    \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def log(*args):\n",
    "    # print(*args)\n",
    "    return\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        q = collections.deque()\n",
    "\n",
    "        def bfs():\n",
    "            step = 0\n",
    "            visit = defaultdict(int)\n",
    "            while len(q) > 0:\n",
    "                size = len(q)\n",
    "                step += 1\n",
    "                while size > 0:\n",
    "                    x, y = q.popleft()\n",
    "                    visit[(x, y)] = 1\n",
    "                    for i in [[0, 1], [1, 0], [-1, 0], [0, -1]]:\n",
    "                        xx = x + i[0]\n",
    "                        yy = y + i[1]\n",
    "                        if xx < 0 or yy < 0 or xx >= len(rooms) or yy >= len(rooms[0]) or rooms[xx][yy] == -1 or \\\n",
    "                                rooms[xx][yy] == 0 or (xx, yy) in visit:\n",
    "                            continue\n",
    "                        # log(xx, yy, rooms[xx][yy])\n",
    "                        rooms[xx][yy] = min(step, rooms[xx][yy])\n",
    "                        log((xx, yy), rooms[xx][yy])\n",
    "                        visit[(xx, yy)] = 1\n",
    "                        q.append((xx, yy))\n",
    "                    size -= 1\n",
    "\n",
    "        for i in range(len(rooms)):\n",
    "            for j in range(len(rooms[0])):\n",
    "                if rooms[i][j] == 0:\n",
    "                    log('---', (i, j))\n",
    "                    q.append((i, j))\n",
    "                    bfs()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        inf = 2**31 - 1\n",
    "        m, n = len(rooms), len(rooms[0])\n",
    "        dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "\n",
    "        def helper(i, j):\n",
    "            vis = [[False] * n for _ in range(m)]\n",
    "            q = deque()\n",
    "            q.append((i, j, 0))\n",
    "            vis[i][j] = True\n",
    "            while q:\n",
    "                x, y, l = q.popleft()\n",
    "                rooms[x][y] = min(rooms[x][y], l)\n",
    "\n",
    "                for dir in dirs:\n",
    "                    nx, ny = x + dir[0], y + dir[1]\n",
    "                    if nx < 0 or nx >= m or ny < 0 or ny >= n:\n",
    "                        continue\n",
    "                    if vis[nx][ny] or rooms[nx][ny] == -1 or rooms[nx][ny] < l + 1:\n",
    "                        continue\n",
    "                    vis[nx][ny] = True\n",
    "                    q.append((nx, ny, l + 1))\n",
    "        \n",
    "        for i, row in enumerate(rooms):\n",
    "            for j, v in enumerate(row):\n",
    "                if v == 0:\n",
    "                    helper(i, j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        m, n = len(rooms), len(rooms[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if rooms[i][j] != 0:\n",
    "                    continue\n",
    "                \n",
    "                self.bfs(rooms, i, j)\n",
    "        \n",
    "    \n",
    "    def bfs(self, rooms: List[List[int]], i: int, j: int):\n",
    "        from collections import deque\n",
    "\n",
    "        m, n = len(rooms), len(rooms[0])\n",
    "        seen = set()\n",
    "        seen.add((i, j))\n",
    "        queue = deque([(i, j)])\n",
    "        distance = 0\n",
    "        while queue:\n",
    "            l = len(queue)\n",
    "            for _ in range(l):\n",
    "                x, y = queue.popleft()\n",
    "                for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:\n",
    "                    new_x, new_y = x + dx, y + dy\n",
    "                    if new_x < 0 or new_x >= m or new_y < 0 or new_y >= n:\n",
    "                        continue\n",
    "                    \n",
    "                    if rooms[new_x][new_y] == -1 or rooms[new_x][new_y] <= distance + 1:\n",
    "                        continue\n",
    "                    \n",
    "                    if (new_x, new_y) in seen:\n",
    "                        continue \n",
    "                    \n",
    "                    queue.append((new_x, new_y))\n",
    "                    seen.add((new_x, new_y))\n",
    "                    rooms[new_x][new_y] = distance + 1\n",
    "            \n",
    "            distance += 1\n",
    "        \n",
    "                \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        \n",
    "\n",
    "\n",
    "        def bfs(rooms: List[List[int]], cur_row: int, cur_column: int):\n",
    "            row, column = len(rooms), len(rooms[0])\n",
    "            queue = [(cur_row, cur_column)]\n",
    "\n",
    "            distance = 0\n",
    "            while queue:\n",
    "                distance += 1\n",
    "                new_queue = []\n",
    "                while queue:\n",
    "                    start_row, start_column = queue.pop()\n",
    "                    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "                    for direction in directions:\n",
    "                        tmp_row = start_row + direction[0]\n",
    "                        tmp_column = start_column + direction[1]\n",
    "                        if tmp_row < row and tmp_row >= 0 and tmp_column < column and tmp_column >=0 and rooms[tmp_row][tmp_column] != -1: \n",
    "                            if rooms[tmp_row][tmp_column] > distance:\n",
    "                                rooms[tmp_row][tmp_column] = distance\n",
    "                                new_queue.append((tmp_row, tmp_column))\n",
    "                queue = new_queue\n",
    "\n",
    "        # USE BFS \n",
    "        row, column = len(rooms), len(rooms[0])\n",
    "        for i in range(row):\n",
    "            for j in range(column):\n",
    "                if rooms[i][j] == 0:\n",
    "                    bfs(rooms, i, j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "WALL = -1\n",
    "DOOR = 0\n",
    "class Solution:\n",
    "    \n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        m, n = len(rooms), len(rooms[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if rooms[i][j] == DOOR:\n",
    "                    self.travel(rooms, i, j)\n",
    "    \n",
    "    def travel(self, rooms, i, j):\n",
    "        m, n = len(rooms), len(rooms[0])\n",
    "        directions = [(1,0), (-1, 0), (0, 1), (0, -1)]\n",
    "        q = deque([(i, j)])\n",
    "        visited = set([i, j])\n",
    "        step = 0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                x, y = q.popleft()\n",
    "               \n",
    "                rooms[x][y] = min(step, rooms[x][y])\n",
    "                for dx, dy in directions:\n",
    "                    newx, newy = x + dx, y + dy\n",
    "                    if self.is_valid(rooms, newx, newy) and (newx, newy) not in visited:\n",
    "                        visited.add((newx, newy))\n",
    "                        q.append((newx, newy))\n",
    "            step += 1\n",
    "\n",
    "    def is_valid(self, rooms, x, y):\n",
    "        if x < 0 or x >= len(rooms) or y < 0 or y >= len(rooms[0]):\n",
    "            return False \n",
    "        if rooms[x][y] == DOOR or rooms[x][y] == WALL:\n",
    "            return False \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        m = rooms.__len__()\n",
    "        n = rooms[0].__len__()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if rooms[i][j] == 0:  # door\n",
    "                    visited = [[0] * n for _ in range(m)]\n",
    "                    # bfs\n",
    "                    q = deque([[i, j, 0]])\n",
    "                    while q:\n",
    "                        row, col, distance = q.popleft()\n",
    "                        # up\n",
    "                        if row - 1 in range(m) and rooms[row - 1][col] > 0 and not visited[row - 1][col]:\n",
    "                            rooms[row - 1][col] = min(rooms[row - 1][col], distance + 1)\n",
    "                            visited[row - 1][col] = 1\n",
    "                            q.append([row - 1, col, distance + 1])\n",
    "                        # down\n",
    "                        if row + 1 in range(m) and rooms[row + 1][col] > 0 and not visited[row + 1][col]:\n",
    "                            rooms[row + 1][col] = min(rooms[row + 1][col], distance + 1)\n",
    "                            visited[row + 1][col] = 1\n",
    "                            q.append([row + 1, col, distance + 1])\n",
    "                        # left\n",
    "                        if col - 1 in range(n) and rooms[row][col - 1] > 0 and not visited[row][col - 1]:\n",
    "                            rooms[row][col - 1] = min(rooms[row][col - 1], distance + 1)\n",
    "                            visited[row][col - 1] = 1\n",
    "                            q.append([row, col - 1, distance + 1])\n",
    "                        # right\n",
    "                        if col + 1 in range(n) and rooms[row][col + 1] > 0 and not visited[row][col + 1]:\n",
    "                            rooms[row][col + 1] = min(rooms[row][col + 1], distance + 1)\n",
    "                            visited[row][col + 1] = 1\n",
    "                            q.append([row, col + 1, distance + 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        \n",
    "        m, n = len(rooms), len(rooms[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if rooms[i][j] == 0:\n",
    "                    q = collections.deque()\n",
    "                    q.append([i, j])\n",
    "\n",
    "                    while q:\n",
    "                        x, y = q.popleft()\n",
    "                        for dx, dy in [[0, 1], [0, -1], [1, 0], [-1, 0]]:\n",
    "                            nx, ny = x + dx, y + dy\n",
    "                            if 0 <= nx < m and 0 <= ny < n and rooms[nx][ny] == 2147483647:\n",
    "                                rooms[nx][ny] = rooms[x][y] + 1\n",
    "                                q.append([nx, ny])\n",
    "\n",
    "                            # if the distance to the gate is less than the current distance, update the distance\n",
    "                            elif 0 <= nx < m and 0 <= ny < n and rooms[nx][ny] > rooms[x][y] + 1:\n",
    "                                rooms[nx][ny] = rooms[x][y] + 1\n",
    "                                q.append([nx, ny])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        m, n = len(rooms), len(rooms[0])\n",
    "        q = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if rooms[i][j] == 0:\n",
    "                    cnt = 1\n",
    "                    q.append((i-1, j, cnt))\n",
    "                    q.append((i+1, j, cnt))\n",
    "                    q.append((i, j-1, cnt))\n",
    "                    q.append((i, j+1, cnt))\n",
    "                    while q:\n",
    "                        r, c, d = q.popleft()\n",
    "                        if r < 0 or r >= m or c < 0 or c >= n:\n",
    "                            continue\n",
    "                        if rooms[r][c] == -1:\n",
    "                            continue \n",
    "                        if rooms[r][c] > d:\n",
    "                            rooms[r][c] = d\n",
    "                            q.append((r-1, c, d+1))\n",
    "                            q.append((r+1, c, d+1))\n",
    "                            q.append((r, c-1, d+1))\n",
    "                            q.append((r, c+1, d+1))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        N = len(rooms)\n",
    "        M = len(rooms[0])\n",
    "        direc = [-1, 0, 1, 0, -1]\n",
    "        def bfs(pos):\n",
    "            visited = set()\n",
    "            q = deque()\n",
    "            q.append(pos)\n",
    "            visited.add(pos)\n",
    "            dist = 0\n",
    "            while q:\n",
    "                num = len(q)\n",
    "                dist += 1\n",
    "                for _ in range(num):\n",
    "                    cur = q.popleft()\n",
    "                    for k in range(4):\n",
    "                        new = (cur[0]+direc[k],cur[1]+direc[k+1])\n",
    "                        if new not in visited and new[0] >=0 and new[0] < N and new[1] >= 0 and new[1] < M and rooms[new[0]][new[1]] > 0:\n",
    "                            visited.add(new)\n",
    "                            q.append(new)\n",
    "                            rooms[new[0]][new[1]] = min(dist, rooms[new[0]][new[1]])\n",
    "        for i in range(N):\n",
    "            for j in range(M):\n",
    "                if rooms[i][j] == 0:\n",
    "                    bfs((i, j))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        queue = []\n",
    "        for i in range(len(rooms)):\n",
    "            for j in range(len(rooms[0])):\n",
    "                if rooms[i][j] == 0:\n",
    "                    queue.append((i, j, 0))\n",
    "        while queue:\n",
    "            r, c, dist = queue.pop(0)\n",
    "            for dr, dc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)):\n",
    "                if 0 <= dr < len(rooms) and 0 <= dc < len(rooms[0]) and rooms[dr][dc] == 2147483647:\n",
    "                    rooms[dr][dc] = dist + 1\n",
    "                    queue.append((dr, dc, dist+1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        m = len(rooms)\n",
    "        n = len(rooms[0])\n",
    "        direct = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "        INF = 2147483647\n",
    "        def check(new_x,new_y):\n",
    "            return new_x < m and new_x >=0 and new_y <n and new_y>=0\n",
    "        queue = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if rooms[i][j] == 0:\n",
    "                    queue.append((i, j, 0))\n",
    "\n",
    "        while queue:\n",
    "            cur_x, cur_y, dis = queue.pop(0)\n",
    "            for di_x,di_y in [[0,1], [1,0], [0,-1], [-1,0]]:\n",
    "                new_x = cur_x + di_x\n",
    "                new_y = cur_y + di_y\n",
    "                if 0<=new_x < m and 0<=new_y<n and rooms[new_x][new_y] ==INF:\n",
    "                    rooms[new_x][new_y] = dis+1\n",
    "                    queue.append((new_x,new_y,dis+1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        #多源BFS模板题\n",
    "        quene=deque()\n",
    "        m,n=len(rooms),len(rooms[0])\n",
    "        vis=[[False]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if rooms[i][j]==0:\n",
    "                    quene.append((i,j,0))\n",
    "                    vis[i][j]=True\n",
    "        directions=[(0,1),(1,0),(-1,0),(0,-1)]\n",
    "        while quene:\n",
    "            x,y,dis=quene.popleft()\n",
    "            rooms[x][y]=min(rooms[x][y],dis)\n",
    "            for i,j in directions:\n",
    "                new_x,new_y=x+i,y+j\n",
    "                if 0<=new_x<m and 0<=new_y<n and rooms[new_x][new_y]>0:\n",
    "                    if not vis[new_x][new_y]:\n",
    "                        vis[new_x][new_y]=True\n",
    "                        quene.append((new_x,new_y,dis+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        empty = (2**31) - 1\n",
    "        r,c  = len(rooms),len(rooms[0])\n",
    "        queue = []\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if rooms[i][j] == 0:\n",
    "                    queue.append([0,i,j])\n",
    "        \n",
    "        dx = [1,-1,0,0]\n",
    "        dy = [0,0,1,-1]\n",
    "        while len(queue)>0:\n",
    "            dis,x,y = queue[0]\n",
    "            queue.pop(0)\n",
    "            for i in range(4):\n",
    "                nx,ny = x+dx[i],y+dy[i]\n",
    "                if 0<=nx<r and 0<=ny<c and rooms[nx][ny]==empty:\n",
    "                    rooms[nx][ny] = dis + 1\n",
    "                    queue.append((dis+1, nx, ny))\n",
    "            pass\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        m, n = len(rooms), len(rooms[0])\n",
    "        INF = 2147483647\n",
    "        directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n",
    "        q, visited = collections.deque(), set()\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if rooms[i][j] == 0:\n",
    "                    q.append((i, j))\n",
    "        \n",
    "        while q:\n",
    "            r, c = q.popleft()\n",
    "            for dr, dc in directions:\n",
    "                nr, nc = r + dr, c + dc\n",
    "                if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in visited and rooms[nr][nc] == INF:\n",
    "                    q.append((nr, nc))\n",
    "                    visited.add((nr, nc))\n",
    "                    rooms[nr][nc] = rooms[r][c] + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        null = 2147483647\n",
    "        m, n = len(rooms), len(rooms[0])\n",
    "        stack = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if rooms[i][j] == 0:\n",
    "                    stack.append([i, j])\n",
    "        step = 1\n",
    "        while stack:\n",
    "            nex = []\n",
    "            for i, j in stack:\n",
    "                for x, y in [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]]:\n",
    "                    if 0 <= x < m and 0 <= y < n and rooms[x][y] == null:\n",
    "                        nex.append([x, y])\n",
    "                        rooms[x][y] = step\n",
    "            step += 1\n",
    "            stack = nex\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        null = 2147483647\n",
    "        m, n = len(rooms), len(rooms[0])\n",
    "        stack = []\n",
    "        #将门存入栈中\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if rooms[i][j] == 0:\n",
    "                    stack.append([i, j])\n",
    "        step = 1\n",
    "        while stack:\n",
    "            nex = []\n",
    "            for i, j in stack:\n",
    "                for x, y in [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]]:\n",
    "                    if 0 <= x < m and 0 <= y < n and rooms[x][y] == null:\n",
    "                        nex.append([x, y])\n",
    "                        rooms[x][y] = step\n",
    "            print(nex,step)\n",
    "            step += 1\n",
    "            stack = nex\n",
    "            \n",
    "        return rooms\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms):\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        Args:\n",
    "            rooms (list[list[int]]):\n",
    "        returns (list[list[int]]): 表示各个位置到达门的最近的距离\n",
    "        \"\"\"\n",
    "        #处理异常情况\n",
    "        if rooms == None or len(rooms) == 0:\n",
    "            return []\n",
    "        \n",
    "        m, n = len(rooms), len(rooms[0])\n",
    "        INT_MAX = 2**31 -1 \n",
    "        gate_poses = []\n",
    "\n",
    "        #从其中一个门开始出发, 到达各个位置的最短距离\n",
    "        dp = [[INT_MAX for _ in range(n)] for _ in range(m)]\n",
    "        \n",
    "        #找出图中所有门的位置, 将问题转化为从各个门为起始位置出发, 到达各个节点的最短距离\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if rooms[i][j] == 0:\n",
    "                    gate_poses.append([i, j])\n",
    "            \n",
    "        # print(\"各个门的位置:\", gate_poses)        \n",
    "        #从其中一个门开始出发, 到达各个位置的最短距离\n",
    "        for gate_pos in gate_poses:\n",
    "            visited = [[False for _ in range(n)] for _ in range(m)]\n",
    "            \n",
    "            rooms[gate_pos[0]][gate_pos[1]] = 0 \n",
    "            visited[gate_pos[0]][gate_pos[1]] = True\n",
    "\n",
    "            self.bfs(gate_poses, rooms, visited)\n",
    "        \n",
    "        # print(rooms)\n",
    "        return \n",
    "\n",
    "    def bfs(self, gate_poses, rooms, visited):\n",
    "        \"\"\"\n",
    "        动态规划求解从[cur_row, cur_col]出发到达各个位置的最短的距离\n",
    "        Args:\n",
    "            cur_row (int):\n",
    "            cur_col (int):\n",
    "            rooms (list[list[int]]):\n",
    "            visited (list[list[bool]])\n",
    "        returns ()\n",
    "        \"\"\"\n",
    "        #使用bfs求解\n",
    "        #每次可以从上下左右四个方向进行移动\n",
    "        directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n",
    "\n",
    "        queue = gate_poses\n",
    "        \n",
    "        while queue:\n",
    "            cur_node = queue.pop(0)\n",
    "            for direction in directions:\n",
    "                new_row = cur_node[0] + direction[0]\n",
    "                new_col = cur_node[1] + direction[1]\n",
    "\n",
    "                #判断该节点是否越界, 若该节点不是墙且未被访问过, 将该节点加入, 更新dp\n",
    "                if 0 <= new_row < len(rooms) and 0 <= new_col < len(rooms[0]) and rooms[new_row][new_col] != -1 and not visited[new_row][new_col]:\n",
    "                    rooms[new_row][new_col] = min(rooms[cur_node[0]][cur_node[1]] + 1, rooms[new_row][new_col])\n",
    "                    visited[new_row][new_col] = True \n",
    "                    queue.append([new_row, new_col])\n",
    "        \n",
    "        return  \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "INF = (2 << 30) - 1\n",
    "# print(INF)\n",
    "dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        q = []\n",
    "        n, m = len(rooms), len(rooms[0])\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if rooms[i][j] == 0:\n",
    "                    q.append((i, j))\n",
    "        step = 0\n",
    "        vis = set()\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x, y in tmp:\n",
    "                rooms[x][y] = step\n",
    "                for dx, dy in dirs:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if -1 < nx < n and -1 < ny < m and ((nx, ny) not in vis) and rooms[nx][ny] == INF:\n",
    "                        # print(nx,)\n",
    "                        vis.add((nx, ny))\n",
    "                        q.append((nx, ny))\n",
    "            step += 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        def bfs(rooms: List[List[int]], start_positions: List[Tuple[int, int]]):\n",
    "            row, column = len(rooms), len(rooms[0])\n",
    "            queue = start_positions\n",
    "            visited_positions = set(queue)\n",
    "\n",
    "            distance = 0\n",
    "            while queue:\n",
    "                distance += 1\n",
    "                new_queue = []\n",
    "                while queue:\n",
    "                    start_row, start_column = queue.pop()\n",
    "                    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "                    for direction in directions:\n",
    "                        tmp_row = start_row + direction[0]\n",
    "                        tmp_column = start_column + direction[1]\n",
    "                        if tmp_row < row and tmp_row >= 0 and tmp_column < column and tmp_column >=0 and (tmp_row, tmp_column) not in visited_positions and rooms[tmp_row][tmp_column] != -1: \n",
    "                            visited_positions.add((tmp_row, tmp_column))\n",
    "                            if rooms[tmp_row][tmp_column] > distance:\n",
    "                                rooms[tmp_row][tmp_column] = distance\n",
    "                                new_queue.append((tmp_row, tmp_column))\n",
    "                queue = new_queue\n",
    "\n",
    "        # USE BFS \n",
    "        row, column = len(rooms), len(rooms[0])\n",
    "        start_list = []\n",
    "        for i in range(row):\n",
    "            for j in range(column):\n",
    "                if rooms[i][j] == 0:\n",
    "                    start_list.append((i, j))\n",
    "        bfs(rooms, start_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validIndex(self, i, j):\n",
    "        if i >= 0 and i < self.m and j >= 0 and j < self.n:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        gateList = []\n",
    "        self.m = len(rooms)\n",
    "        self.n = len(rooms[0])\n",
    "        for i in range(self.m):\n",
    "            for j in range(self.n):\n",
    "                if rooms[i][j] == 0:\n",
    "                    gateList.append((i, j))\n",
    "\n",
    "        if len(gateList) == 0:\n",
    "            return\n",
    "        else:\n",
    "            visited = [[0 for j in range(self.n)] for i in range(self.m)]\n",
    "            q = collections.deque()\n",
    "            for (i, j) in gateList:\n",
    "                q.append([i, j, 0])\n",
    "                visited[i][j] = 1\n",
    "\n",
    "            while len(q):\n",
    "                top = q.popleft()\n",
    "                i, j, depth = top[0], top[1], top[2]\n",
    "                if rooms[i][j] == -1:\n",
    "                    continue\n",
    "                else:\n",
    "                    if rooms[i][j] == 2147483647:\n",
    "                        rooms[i][j] = depth\n",
    "                    if self.validIndex(i-1, j) and not(visited[i-1][j]):\n",
    "                        visited[i-1][j] = 1\n",
    "                        q.append([i-1, j, depth+1])\n",
    "                    if self.validIndex(i, j-1) and not(visited[i][j-1]):\n",
    "                        visited[i][j-1] = 1\n",
    "                        q.append([i, j-1, depth+1])\n",
    "                    if self.validIndex(i+1, j) and not(visited[i+1][j]):\n",
    "                        visited[i+1][j] = 1\n",
    "                        q.append([i+1, j, depth+1])\n",
    "                    if self.validIndex(i, j+1) and not(visited[i][j+1]):\n",
    "                        visited[i][j+1] = 1\n",
    "                        q.append([i, j+1, depth+1])\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        INF=2147483647\n",
    "        m=len(rooms)\n",
    "        n=len(rooms[0])\n",
    "        stack=deque()\n",
    "        for n1 in range(m):\n",
    "            for n2 in range(n):\n",
    "                if rooms[n1][n2]==0:\n",
    "                    stack.append((n1 - 1, n2, 1)) if 0 <= n1 - 1 < m and 0 <= n2 < n else 0\n",
    "                    stack.append((n1 + 1, n2, 1)) if 0 <= n1 + 1 < m and 0 <= n2 < n else 0\n",
    "                    stack.append((n1, n2 - 1, 1)) if 0 <= n1 < m and 0 <= n2 - 1 < n else 0\n",
    "                    stack.append((n1, n2 + 1, 1)) if 0 <= n1 < m and 0 <= n2 + 1 < n else 0\n",
    "        while stack:\n",
    "            n1,n2,distance=stack.popleft()\n",
    "            if rooms[n1][n2]==INF:\n",
    "                rooms[n1][n2]=distance\n",
    "                stack.append((n1-1,n2,distance+1)) if 0<=n1-1<m and 0<=n2<n else 0\n",
    "                stack.append((n1+1,n2,distance+1)) if 0<=n1+1<m and 0<=n2<n else 0\n",
    "                stack.append((n1,n2-1,distance+1)) if 0<=n1<m and 0<=n2-1<n else 0\n",
    "                stack.append((n1,n2+1,distance+1)) if 0<=n1<m and 0<=n2+1<n else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        R, C = len(rooms), len(rooms[0])\n",
    "        q, visited = deque(), set()\n",
    "        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        for r in range(R):\n",
    "            for c in range(C):\n",
    "                if rooms[r][c] == 0:\n",
    "                    q.append((r, c))\n",
    "                    visited.add((r, c))\n",
    "\n",
    "        while q:\n",
    "            r, c = q.popleft()\n",
    "            for dr, dc in directions:\n",
    "                row, col = r + dr, c + dc\n",
    "                if 0 <= row < R and 0 <= col < C and (row, col) not in visited and rooms[row][col] != -1:\n",
    "                    q.append((row, col))\n",
    "                    visited.add((row, col))\n",
    "                    rooms[row][col] = rooms[r][c] + 1\n",
    "        return rooms\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        rows, cols = len(rooms), len(rooms[0])\n",
    "        visit = set()\n",
    "        q =deque()\n",
    "        def addroom(r,c):\n",
    "            if (r<0 or r==rows or c<0 or c==cols or (r,c) in visit or rooms[r][c] == -1):\n",
    "                return\n",
    "            visit.add((r,c))\n",
    "            q.append([r,c])\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                if rooms[r][c] == 0:\n",
    "                    q.append([r,c])\n",
    "                    visit.add((r,c))\n",
    "        dist = 0\n",
    "        while q:\n",
    "            for i in range(len(q)):\n",
    "                r,c = q.popleft()\n",
    "                rooms[r][c] = dist\n",
    "                addroom(r+1, c)\n",
    "                addroom(r-1, c)\n",
    "                addroom(r, c+1)\n",
    "                addroom(r, c-1)\n",
    "            dist +=1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        inf = 2147483647\n",
    "        rows, cols = len(rooms), len(rooms[0])\n",
    "        \n",
    "        visited = set()\n",
    "        def dfs(row, col, dist):\n",
    "            visited.add((row, col))\n",
    "            rooms[row][col] = min(dist, rooms[row][col])\n",
    "            for di, dj in [(-1, 0), (1, 0), (0, 1), (0, -1)]:\n",
    "                if 0 <= row+di < rows and 0 <= col+dj < cols and rooms[row+di][col+dj] != -1 and (row+di, col+dj) not in visited and rooms[row+di][col+dj] > dist+1:\n",
    "                    dfs(row+di, col+dj, dist+1)\n",
    "            visited.remove((row, col))\n",
    "        \n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if rooms[i][j] == 0:\n",
    "                    dfs(i, j, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        directions = [(0,1), (1,0), (0,-1), (-1,0)]\n",
    "        row, col = len(rooms), len(rooms[0])\n",
    "        max_val = row * col\n",
    "\n",
    "        def get_all_door(rooms):\n",
    "            doors_indexes = []\n",
    "            for i in range(row):\n",
    "                for j in range(col):\n",
    "                    if not rooms[i][j] == 0:\n",
    "                        continue\n",
    "                    doors_indexes.append((i, j))\n",
    "            return doors_indexes\n",
    "\n",
    "        def is_cur_loc_valid(cur_i, cur_j):\n",
    "            return 0 <= cur_i < row and 0 <= cur_j < col and rooms[cur_i][cur_j] > max_val\n",
    "\n",
    "        def process_cur_loc(cur_i, cur_j, step):\n",
    "            rooms[cur_i][cur_j] = step\n",
    "\n",
    "        queue = get_all_door(rooms)\n",
    "        seen = set()\n",
    "        step = 1\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                cur_loc = queue.pop(0)\n",
    "                # print('cur_loc', cur_loc)\n",
    "                for direction in directions:\n",
    "                    nex_i, nex_j = cur_loc[0] + direction[0], cur_loc[1] + direction[1]\n",
    "                    if (nex_i, nex_j) in seen:\n",
    "                        continue\n",
    "                    seen.add((nex_i, nex_j))\n",
    "                    if not is_cur_loc_valid(nex_i, nex_j):\n",
    "                        continue\n",
    "                    process_cur_loc(nex_i, nex_j, step)\n",
    "                    queue.append((nex_i, nex_j))\n",
    "            step += 1\n",
    "        # print(rooms)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wallsAndGates(self, rooms: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify rooms in-place instead.\n",
    "        \"\"\"\n",
    "        directions = [(0,1), (1,0), (0,-1), (-1,0)]\n",
    "        row, col = len(rooms), len(rooms[0])\n",
    "        max_val = row * col\n",
    "\n",
    "        def get_all_door(rooms):\n",
    "            doors_indexes = []\n",
    "            for i in range(row):\n",
    "                for j in range(col):\n",
    "                    if not rooms[i][j] == 0:\n",
    "                        continue\n",
    "                    doors_indexes.append((i, j))\n",
    "            return doors_indexes\n",
    "\n",
    "        def is_cur_loc_valid(cur_i, cur_j):\n",
    "            return 0 <= cur_i < row and 0 <= cur_j < col and rooms[cur_i][cur_j] > max_val\n",
    "\n",
    "        def process_cur_loc(cur_i, cur_j, step):\n",
    "            rooms[cur_i][cur_j] = step\n",
    "\n",
    "        queue = get_all_door(rooms)\n",
    "        seen = set()\n",
    "        step = 1\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                cur_loc = queue.pop(0)\n",
    "                print('cur_loc', cur_loc)\n",
    "                for direction in directions:\n",
    "                    nex_i, nex_j = cur_loc[0] + direction[0], cur_loc[1] + direction[1]\n",
    "                    if (nex_i, nex_j) in seen:\n",
    "                        continue\n",
    "                    seen.add((nex_i, nex_j))\n",
    "                    if not is_cur_loc_valid(nex_i, nex_j):\n",
    "                        continue\n",
    "                    process_cur_loc(nex_i, nex_j, step)\n",
    "                    queue.append((nex_i, nex_j))\n",
    "            step += 1\n",
    "        print(rooms)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
